import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.CsvSource;

/**
 * 通配符匹配
 * 题目：给定一个字符串(s) 和一个字符模式(p) ，实现一个支持'?'和'*'的通配符匹配。
 * <p>
 * '?' 可以匹配任何单个字符。
 * '*' 可以匹配任意字符串（包括空字符串）。
 * 两个字符串完全匹配才算匹配成功。
 * <p>
 * 说明:
 * s可能为空，且只包含从a-z的小写字母。
 * p可能为空，且只包含从a-z的小写字母，以及字符?和*。
 * <p>
 * 示例1:
 * 输入:
 * s = "aa"
 * p = "a"
 * 输出: false
 * 解释: "a" 无法匹配 "aa" 整个字符串。
 * <p>
 * 示例2:
 * 输入:
 * s = "aa"
 * p = "*"
 * 输出: true
 * 解释:'*' 可以匹配任意字符串。
 * <p>
 * 示例3:
 * 输入:
 * s = "cb"
 * p = "?a"
 * 输出: false
 * 解释:'?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。
 * <p>
 * 示例4:
 * 输入:
 * s = "adceb"
 * p = "*a*b"
 * 输出: true
 * 解释:第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".
 * <p>
 * 示例5:
 * 输入:
 * s = "acdcb"
 * p = "a*c?b"
 * 输出: false
 * 通过次数55,349提交次数176,036
 * <p>
 * 来源：力扣（LeetCode-44）
 * 链接：https://leetcode-cn.com/problems/wildcard-matching
 *
 * @author godfrey
 * @since 2020-10-20
 */
@DisplayName("通配符匹配")
public class WildcardMatching extends BaseTest {

    @DisplayName("动态规划-时间复杂度：O(mn),空间复杂度：O(mn)")
    @ParameterizedTest
    @CsvSource({"aa,*a", "adceb,*a*b"})
    void matchString(final String s, final String p) {
        //循环次数
        final int m = s.length();
        final int n = p.length();
        //f[i][j]表示s中前i个字符和p中的前j个字符匹配
        boolean[][] f = new boolean[m + 1][n + 1];

        //边界
        f[0][0] = true;

        for (int i = 1; i <= n; ++i) {
            if (p.charAt(i - 1) == '*') {
                f[0][i] = true;
            } else {
                break;
            }
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p.charAt(j - 1) == '*') {
                    f[i][j] = f[i][j - 1] || f[i - 1][j];
                } else if (p.charAt(j - 1) == '?' || s.charAt(i - 1) == p.charAt(j - 1)) {
                    f[i][j] = f[i - 1][j - 1];
                }
            }
        }
        System.out.println(f[m][n]);
    }

    @DisplayName("贪心算法：")
    @ParameterizedTest
    @CsvSource({"aa,*a", "adceb,*a*b"})
    void matchString2(final String s, final String p) {
        //TODO:编写贪心算法
    }
}
